package java学习.代码随想录.动态规划.背包;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/28 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 多重背包 {
    public static int multipack(int[] weight,int[] value,int[] nums,int bagWeight ){

        int[]dp = new int[bagWeight+1];
        // 先物品再背包
        for (int i = 0; i < weight.length ; i++) {
            for (int j = bagWeight; j >=weight[i] ; j--) {
//                根据题意，k：每件物品的数量要与 物品相对应
                for (int k = 1; k <= nums[i]; k++) {
                    if(j - k*weight[i]>=0){

                        dp[j] = Math.max( dp[j] , dp[j - k*weight[i]]+k*value[i] ) ;
                    }
                }
                System.out.println(Arrays.toString(dp));

            }
        }
        return dp[bagWeight];
    }

    /**
     * 若nums数组元素 >1 则 weight、value都加一次。
     */
    public static int multipack1(int[] weight,int[] value,int[] nums,int bagWeight ){
        int[]dp = new int[bagWeight+1];
        List<Integer> w = Arrays.stream(weight).boxed().collect(Collectors.toList());
        List<Integer> v = Arrays.stream(value).boxed().collect(Collectors.toList());
        for (int i = 0; i <nums.length ; i++) {
            while (nums[i]>1){
                w.add(w.get(i));
                v.add(v.get(i));
                nums[i]--;
            }

        }
        for (int i = 0; i < w.size(); i++) {
            for (int j = bagWeight; j >=w.get(i) ; j--) {
                dp[j] = Math.max(dp[j],dp[j-w.get(i)]+v.get(i));
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[bagWeight];
    }


        public static void testMultiPack2() {
        // 版本二：改变遍历个数
        int[] weight = new int[]{1, 3, 4};
        int[] value = new int[]{15, 20, 30};
        int[] nums = new int[]{2, 3, 2};
        int bagWeight = 10;

        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) { // 遍历物品
            for (int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
                // 以上为01背包，然后加一个遍历个数
                for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
                System.out.println(Arrays.toString(dp));
            }
        }
    }
    public static void main(String[] args) {
        int[] weight = new int[] {1, 3, 4};
        int[] value = new int[] {15, 20, 30};
        int[] nums = new int[] {2, 3, 2};
        int bagWeight = 10;
        System.out.println(multipack(weight,value,nums,bagWeight));
//        testMultiPack2();
        System.out.println(multipack1(weight,value,nums,bagWeight));

    }
}
